//
//  155_最小栈.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/8.
/**
 https://leetcode.cn/problems/min-stack/description/
 
 */

import UIKit
// 用栈实现
class MinStack {

    private var stack1 = [Int]() // 正常栈
    private var stack2 = [Int]() // 最小栈
    private var minNum: Int = Int.max // 最小值
    private var size = 0
    
    func push(_ val: Int) {
        stack1.append(val)
        minNum = min(minNum, val)
        stack2.append(minNum)
    }
    
    func pop() {
        stack1.removeLast()
        stack2.removeLast()
        minNum = stack2.last ?? Int.max
    }
    
    func top() -> Int {
        stack1.last ?? 0
    }

    func getMin() -> Int {
        stack2.last ?? 0
    }
}


/// 用链表实现
class MinStack1 {

    private var head: MinStackNode? = MinStackNode(0, Int.max)
    
    func push(_ val: Int) {
        let minNum = min(val, head?.minNum ?? Int.max)
        head = MinStackNode(val, minNum, head )
    }
    
    func pop() {
        head = head?.next
    }
    
    func top() -> Int {
        head?.val ?? Int.max
    }

    func getMin() -> Int {
        head?.minNum ?? Int.max
    }

}
fileprivate class MinStackNode {
    let val: Int // 值
    let minNum: Int // 对应的最小值
    var next: MinStackNode? // 下一个站点
    init(_ val: Int, _ minNum: Int, _ next: MinStackNode? = nil) {
        self.val = val
        self.minNum = minNum
        self.next = next
    }
}

